It is needless to mention how fast new data processing applications are being requested throughout the world. This implies an increase in data communications and storage requirements and correlative traffic jamming and memory saturations.
One solution to those problems is provided by technical means for minimizinq the bit rates required to diqitally express (encode) the processed data while keeping the encoded data quality optimal to the user.
For that purpose, means for compressing the bit rates required for digitally encoding any kind of data are being eagerly looked for.
More generally speaking, let x(t)=x.sub.1, x.sub.2, . . . , x.sub.t, be a string or flow of symbols (symbol being herein taken in a fairly broad sense to include printed characters, image pixels etc . . .), wherein xt is the current symbol and x.sub.1, x2 are past symbols all taken within a predefined family of symbols A=(a.sub.1, a.sub.2, . . . , ad) including a predefined number (d) of different symbols.
Efficient methods have been provided for sequentially coding said string of synbols. For instance, one may refer to U.S. Pat. No. 4,652,856 wherein the flow of symbols is sequentially processed within a Modelling Unit (12) feeding an Encoding Unit (14) to achieve data compression (see FIG. 1 of the above cited US reference).
A particularly valuable Encoding Unit based on arithmetic coding theory is fully described in the above mentioned US Patent.
However, efficient modelling is obviously a critical feature within the overall coding process. To achieve such a modelling, a so called "context" dependent method has been proposed by J. Rissanen in the lBM Technical Disclosure Bulletin Vol. 25 N.degree. Oct. 5, 1991 pp 2462-2464. To that end, the coding of any current symbol x.sub.t takes into consideration hoth past symbols within the considered string, and a so called "influence", or rather relative influence, of past symbols over current symbol coding. The context is defined according to a reordering of past symbols thought to have "influence" on current symbol, with the most influencing symbol considered first, then considering the next to most influencing, and so on.
Rissanen's method collects in a "tree" the number of times or "counts" each symbol of the string being processed occurs at various contexts or states. Modelling operations involve growing the tree in correlation with the consecutive symbols occurrences within the string by assigning each tree "node" with count facilities, taking also into consideration the mentioned influence criteria.
ln Rissanen's method, however, the context tree grows beyond any bound as the tree grows, and so does the required storage for implementing the method. Obviously, this is a main drawback to any actual implementation of said method or process from a practical standpoint.